#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int ep = 0;
int start, cnt;

struct LINK
{
    int s, e, order;
    int val;
};

LINK arr[100005];

struct EDGE
{
    int s, e;
    EDGE *next;
} edges[100005];

struct NODE
{
    int val;
    EDGE *first;
} nodes[100005];

void addedge(int s, int e, int val)
{
    edges[ep].s = s;
    edges[ep].e = e;
    edges[ep].next = nodes[s].first;
    nodes[s].first = &edges[ep];
    nodes[s].val = val;
    ep++;
}

bool mycmp(const LINK &l1, const LINK &l2)
{
    return l1.order < l2.order;
}

int main()
{
    cin >> start >> cnt;
    for (int i = 0; i < cnt; i++)
    {
        int s, val, e;
        cin >> s >> val >> e;
        addedge(s, e, val);
    }
    EDGE *e = nodes[start].first;
    int pos = 0;
    while (1)
    {
        //按链表顺序存到arr中
        arr[pos].s = e->s;
        arr[pos].e = e->e;
        arr[pos].val = nodes[e->s].val;
        pos++;
        if (e->e == -1)
        {
            break;
        }
        e = nodes[e->e].first;
    }
    int left = 0;
    int right = pos - 1;
    int order = 0;//更新好arr里链表的前后元素后还没改变arr里的顺序，给一个权重来排序然后打印
    while (left <= right)
    {
        arr[right].e = arr[left].s;
        arr[right].order = order;
        arr[left].e = arr[right - 1].s;
        arr[left].order = order + 1;
        right--;
        left++;
        order += 2;
    }
    arr[left - 1].e = -1;
    sort(arr, arr + pos, mycmp);
    for (int i = 0; i < pos; i++)
    {
        printf("%05d %d ", arr[i].s, arr[i].val);
        if (arr[i].e == -1)
        {
            printf("-1\n");//-1不能用%05d，会打印成-0001
        }
        else
        {
            printf("%05d\n", arr[i].e);
        }
    }
    return 0;
}